package class3;

import common.ListNode;
import common.ListNodeUtils;

/**
 * https://leetcode.cn/problems/rotate-list/description/
 * 旋转链表
 * 描述：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 * 思路：
 * 1.先遍历链表，计算出链表长度和尾部节点
 * 2.首尾相连形成环，使得我们能够绕着链表来旋转
 * 3.找到新的尾节点和头节点：我们需要找到旋转后链表的尾节点，并且从尾节点的下一个节点开始，它就是新的头节点。
 */
public class Code24_RotateRight {
    public static void main(String[] args) {
        ListNode head = ListNodeUtils.getLinked(1, 2, 3, 4, 5, 6, 7); // 5 6 7 1 2 3 4
        int k = 3; // 7-3 = 4

        ListNode res = rotateRight(head, k);
        ListNodeUtils.print(res);
    }

    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        int n = 1; // 计算链表长度
        ListNode cur = head;
        while (cur.next != null) { // 遍历至倒数第一个节点
            cur = cur.next;
            n++;
        }
        k = k % n; // n实际右移位数
        if (k == 0) { // 当趋于为0时，不需要旋转
            return head;
        }
        cur.next = head;// 构建成环
        ListNode newTail = head; //新的尾部为头节点
        for (int i = 1; i < n - k; i++) { // n - k 为尾节点
            newTail = newTail.next;
        }
        ListNode newHead = newTail.next;
        newTail.next = null;
        return newHead;
    }
}
